public class LongestValidParentheses {

    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n == 0 || n == 1) return 0;
        char[] chars = s.toCharArray();
        int[] dp = new int[n];
        dp[0] = 0;
        if (chars[0] == '(' && chars[1] == ')') dp[1] = 2;
        int max = dp[1];
        for (int i = 2; i < n; i++) {
            if (chars[i] == '(') continue;
            if (i - 1 - dp[i - 1] >= 0 && chars[i - 1 - dp[i - 1]] == '(') {
                dp[i] = dp[i - 1] + 2;
                if (i - 1 - dp[i - 1] - 1 >= 0) dp[i] += dp[i - 1 - dp[i - 1] - 1];
            }
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}
